Medium (4)

1. Two Sum
   1. 20 March, 2026: 00.04.18 ❌
      • Return wrong index
      • BruteForce: $O(n^2)$
      • Better: $O(n)$
      • Optimal: $O(n) + nlogn$
      • unordered_map: easy to access
      • map: sorted useage
2. Sort Color
   • left → tracks position for 0
   • mid → current element
   • right → tracks position for 2
   • 0 → swap with left, move both
   • 1 → just move mid
   • 2 → swap with right, move right only
3. Majority Element
   1. 20 March, 2026: 00.05.43 ✔
      • Boyer–Moore process only gives candidates, not confirmed answers. You must count again to verify and compare with thresold
4. Kadane's Algorithm
   1. 20 March, 2026: 00.05.54 ✔
      • Implment bruteforce and better approach
      • place the condition in appropriate order
5. Print Sub Array

• In Kadane’s algorithm, you reset when the cumulative sum becomes negative, not when the current element is negative.
• Handle tie-breaking rules
  • Prefer longer length
  • If still tied → earlier starting index

6. Stock Buy And Sell
7. Rearrange Array Elements by Sign
   1. 07 April, 2026: 00.12.03 ❌
      • Failed at optimization
        • Instead of two container, use single container
8. Next Permuation
   1. 07 April, 2026: 00.45.54 ❌
      • Failed at implementation
        • We want the next slightly bigger arrangement, not just any bigger one.
        • We do this by modifying the sequence from the right side, because:
          • The right side changes more frequently in lexicographic order.
        1. First decreasing element from right
           Scan from right → left and find the first index i where:

           nums[i] < nums[i + 1]

           i       = 0 1 2 3 4 5
           nums[i] = 1 2 3 6 5 4
           
           i = 2 | 3 < 6  ✅

        Breakpoint at index i = 2 (value = 3)
        • The right side is non-increasing.
        • That means it's already the largest possible arrangement of that suffix.
        • So we must modify something to the left.
        2. Find the "just larger" number to swap
           • From the right side ([6, 5, 4]), find the smallest number greater than nums[i] = 3.
           • We want the next smallest increase, not a big jump.
           • For 3, candidates on right: 4, Smallest > 3 → 4
        3. Swap nums[i] with that number

           1 2 4 6 5 3

           Now we increased the number slightly.
        4. Reverse the suffix Reverse everything to the right of index i = 2

           1 2 4 | 6 5 3  → reverse → 1 2 4 | 3 5 6

           • The suffix was in descending order (largest)
           • Reversing keeps it as the smallest possible arrangement
        • Edge Case: Already Largest Permutation If no breakpoint exists:

          6 5 4 3 2 1

          Entire array is descending → largest permutation
          Solution: Reverse whole array

          1 2 3 4 5 6

9. Array Leaders
10. Longest Consecutive Sequences
11. Set Zeros
12. Rotate Matrix 90 Degree
    1. 07 April, 2026: 00.5.41 ❌
       • Failed at optimization
         • bottom left -> top right became result diagnal
         • left lower value became upper right value
13. Print Spiral Manner
    1. 07 April, 2026: 00.26.54 ❌
       • Failed at implementation
         • 4 iterator is 4 index
         • Handle cases for matrices like 1xN or Nx1, you may duplicate elements.